class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        int row = matrix.size(),low=matrix[0].size();
        int x=0,y=low-1;
        while(x>=0&&x<row&&y>=0&&y<low)
        {
            if(target<matrix[x][y]) --y;
            else if(target>matrix[x][y]) ++x;
            else return true;
        }
        return false;
    }
};